package com.sicheng.lc.杂题;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/24 16:32
 */
public class 情侣牵手 {
    //https://leetcode.cn/problems/couples-holding-hands/

    int[] p = new int[61];

    int n;

    void init(int n) {
        this.n = n;
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
    }

    int find(int x) {
        if (p[x] == x)
            return x;
        p[x] = find(p[x]);
        return p[x];
    }

    void union(int a, int b) {
        int pa = find(a), pb = find(b);
        p[pa] = pb;
    }

    public int minSwapsCouples(int[] row) {
        int n = row.length >> 1;
        init(n);

        for (int i = 0; i < row.length; i += 2) {
            union(row[i] / 2, row[i + 1] / 2);
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (p[i] == i) {
                cnt++;
            }
        }
        return n - cnt;
    }

    public static void main(String[] args) {
        情侣牵手 solution = new 情侣牵手();
        int[] rows = {3, 6, 0, 2, 1, 8, 4, 5, 7, 9};
        System.out.println(solution.minSwapsCouples(rows));
    }
}
